题解 P3604 【美好的每一天】

发表于 | 更新于

$Description$

一个区间如果满足区间内的值重排之后可以成为一个回文串，则这个区间可以回归天空

当前有$m$个区间，要求每个区间中有多少个子区间可以回归天空

$Solution$

很容易想到是莫队题，但是对于维护区间贡献很难处理。

由于区间内的字符都是小写字母，考虑用$2$的幂次表示，如$’a’$表示为$2^0$,$’b’$表示为$2^1$,$’z’$表示为$2^{25}$(用$2$的幂次表示的原因下会讲)

然后考虑一个区间$[l,r]$对答案有贡献当且仅当$a_{r}~xor~a_{l-1}=2^x$或$0$，其中$a_{i}$为异或前缀和

开一个计数数组$c$,其中$c_{i}$表示当前区间中异或前缀和的值为$i$的点的个数，统计答案时若当前枚举到的点$j$的异或前缀和为$a_{j}$，枚举$2$的所有幂次和$0$,$ans$直接加上(或减去)$c[a_{j}]+\sum\limits_{i=0}^{25}c[2^i~xor~a_{j}]$

至于为什么区间内字符用$2$的幂次表示,换用别的编号呢$?$

如果不用$2$的幂次表示,换用别的编号，那么即使$xor$起来$=0$也不能说明区间内的数能排列成回文串,如一个区间内三个数的的编号分别为$1,4,5$,即使它们异或起来也是$0$，但是它们显然不能构成回文串。

$PS:$当前维护$[l,r]$的信息时，$ans$应加上$[l-1,r-1]$的信息(若是减去则维护$[l-1,r]$的信息)，并且桶维护$[l-1,r]$的信息,因为当前枚举到的点是$r$。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 60007
using namespace std;
struct node{
    int l,r,num;
}q[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int ans,block,n,m,w[N],a[N],Ans[N];
unsigned short c[1<<26];
char s[N];
inline bool cmp(node a,node b){
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
inline void add(int k){
    for (int i=0;i<26;++i)
        ans+=c[k^(1<<i)];
    ans+=c[k];
    ++c[k];
}
inline void del(int k){
    for (int i=0;i<26;++i)
        ans-=c[k^(1<<i)];
    --c[k];
    ans-=c[k];
}
signed main(){
    n=read(),m=read();block=(m&&n/sqrt(m*2/3))?n/sqrt(m*2/3):sqrt(n);
    scanf("%s",s+1);
    for (int i=1;i<=n;++i)w[i]=(1<<(s[i]-'a')),a[i]=a[i-1]^w[i];
    for (int i=1;i<=m;++i)q[i].l=read()-1,q[i].r=read(),q[i].num=i;
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for (int i=1;i<=m;++i){
        int ql=q[i].l,qr=q[i].r;
        while (l>ql)add(a[--l]);
        while (r<qr)add(a[++r]);
        while (l<ql)del(a[l++]);
        while (r>qr)del(a[r--]);
        Ans[q[i].num]=ans;
    }
       for (int i=1;i<=m;++i)printf("%d\n",Ans[i]);
    return 0;
}